/*Sean Waitkus Program 2 RadixSort
This class takes an array of n integers and radix sorts them from lowest to highest using linked lists
formatted using eclipse
 */
import java.util.LinkedList;

public class RadixSort {
	// I tried to initialize these via a for loop but I was unsuccessful
	// Initializes the buckets
	@SuppressWarnings("rawtypes")
	private static LinkedList[] bucket = { 
			new LinkedList(), // -9
			new LinkedList(), // -8
			new LinkedList(), // -7
			new LinkedList(), // -6
			new LinkedList(), // -5
			new LinkedList(), // -4
			new LinkedList(), // -3
			new LinkedList(), // -2
			new LinkedList(), // -1
			new LinkedList(), // 0
			new LinkedList(), // 1
			new LinkedList(), // 2
			new LinkedList(), // 3
			new LinkedList(), // 4
			new LinkedList(), // 5
			new LinkedList(), // 6
			new LinkedList(), // 7
			new LinkedList(), // 8
			new LinkedList() // 9
	};

	@SuppressWarnings("unchecked")
	public static void radixSort(int[] list) {

		// Get the total number of digits of the largest int n
		int totalDigits = getTotalDigits(list);

		// loops through the list depending on the number of digits.
		
		for (int k = 1; k <= totalDigits; k++) {
			int radix;
			// gets the current digit adds 9 to it and assigns it a bucket based
			// on its radix
			for (int j = 0; j < list.length; j++) {
				radix = getCurrentDigit(list[j], k) + 9;

				// places the digit in the appropriate bucket
				bucket[radix].offer(list[j]);

			}

			// goes through the buckets and puts the values back in the list
			int x = 0;
			for (int i = 0; i < bucket.length; i++) {
				while (bucket[i].peek() != null) {
					list[x++] = (Integer) bucket[i].poll();
				}
			}
		}

	}

	// gets the maximum digits of the numbers in the list sets the largest
	// amount of digits and returns max digits
	public static int getTotalDigits(int[] list) {

		int totalDigits = 0;
		int digits;
		for (int i = 0; i < list.length; i++) {

			digits = getDigits(list[i]);
			if (digits > totalDigits) {

				totalDigits = digits;
			}
		}
		return totalDigits;
	}

	// gets the number of digits of int i
	public static int getDigits(int i) {

		if (i < 10) {

			return 1;
		}

		return 1 + getDigits(i / 10);
	}

	/*
	 * gets the digit at the specified index of a given number and returns that
	 * digitmy intention was to come back to this and figure out the "divisor"
	 * aproach
	 */
	public static int getCurrentDigit(int num, int radix) {

		return (int) (num / Math.pow(10, radix - 1)) % 10;

	}

}// end radix sort

